﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 6031)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//malloc出的链表
//typedef struct sl
//{
//	int val;
//	struct sl* next;
//}sl;
//
//sl* test1()		//链表的创建
//{
//	sl* p1 = (sl*)malloc(sizeof(sl));
//	/*if (!p1)
//	{
//		return;
//	}*/
//	assert(p1);
//	sl* p2 = (sl*)malloc(sizeof(sl));
//	assert(p2);
//	sl* p3 = (sl*)malloc(sizeof(sl));
//	assert(p3);
//	sl* p4 = (sl*)malloc(sizeof(sl));
//	assert(p4);
//
//	p1->next = p2;
//	p2->next = p3;
//	p3->next = p4;
//	p4->next = NULL;
//
//    p1->val = 1;
//    p2->val = 3;
//    p3->val = 3;
//    p4->val = 4;
//
//    return p1;
//}
//
//void print(sl* head)
//{
//	sl* cur = head;
//	while (cur)
//	{
//		printf("%d ", cur->val);
//		cur = cur->next;
//	}
//}



//删除指定数（删除结点）
//sl* removeElements(sl* head, int val) 
//{
//    sl* per = NULL;
//    sl* cur = head;
//    while (cur)
//    {
//        if (cur->val == val)
//        {
//            if (per)
//            {
//                per->next = cur->next;
//                free(cur);
//                cur = per->next;
//            }
//            else
//            {
//                struct ListNode* tail = cur;
//                cur = cur->next;
//                head = cur;
//                free(tail);
//            }
//        }
//        else
//        {
//            per = cur;
//            cur = cur->next;
//        }
//    }
//    return head;
//}

//删除指定数（拿下来尾插）
//typedef struct ListNode sl;
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    sl* rhead = NULL;
//    sl* tail = NULL;
//    sl* cur = head;
//    while (cur)
//    {
//        if (cur->val != val)
//        {
//            if (!tail)
//            {
//                rhead = tail = cur;
//            }
//            else
//            {
//                tail->next = cur;
//                tail = tail->next;
//            }
//            cur = cur->next;
//        }
//        else
//        {
//            cur = cur->next;
//        }
//    }
//    if (tail)
//        tail->next = NULL;
//    return rhead;
//}


//找交界点
//typedef struct ListNode sl;
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    sl* tailA = headA;
//    sl* tailB = headB;
//    int lenA = 0;
//    int lenB = 0;
//    while (tailA->next)
//    {
//        tailA = tailA->next;
//        lenA++;
//    }
//    while (tailB->next)
//    {
//        tailB = tailB->next;
//        lenB++;
//    }
//    if (tailA != tailB)
//    {
//        return NULL;
//    }
//    int gap = abs(lenA - lenB);
//    sl* longsl = headA;
//    sl* shortsl = headB;
//    if (lenA < lenB)
//    {
//        longsl = headB;
//        shortsl = headA;
//    }
//
//    while (gap--)
//    {
//        longsl = longsl->next;
//    }
//
//    while (longsl != shortsl)
//    {
//        longsl = longsl->next;
//        shortsl = shortsl->next;
//
//    }
//    return longsl;
//}


//反转链表（后指前）
//typedef struct ListNode sl;
//struct ListNode* reverseList(struct ListNode* head)
//{
//    sl* rhead = NULL;
//    sl* cur = head;
//    while (cur)
//    {
//        sl* next = cur->next;
//
//        cur->next = rhead;
//        rhead = cur;
//
//        cur = next;
//    }
//    return rhead;
//}

//反转链表（拿下来头插）
//typedef struct ListNode sl;
//struct ListNode* reverseList(struct ListNode* head) {
//    if (!head)
//        return NULL;
//    sl* cur = head;
//    sl* next = head->next;
//    sl* tail = NULL;
//    while (cur)
//    {
//        if (!tail)
//        {
//            tail = head;
//            tail->next = NULL;
//        }
//        else
//        {
//            cur->next = tail;
//            tail = cur;
//        }
//        cur = next;
//        if (next)
//            next = next->next;
//    }
//    return tail;
//}

//合并链表（不带头）
//typedef struct ListNode sl;
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    if (!list1)
//        return list2;
//    if (!list2)
//        return list1;
//
//
//    sl* head = NULL;
//    sl* tail = NULL;
//
//    while (list1 && list2)
//    {
//        if (list1->val > list2->val)
//        {
//            if (!tail)
//            {
//                head = tail = list2;
//            }
//            else
//            {
//                tail->next = list2;
//                tail = tail->next;
//            }
//            list2 = list2->next;
//        }
//        else
//        {
//            if (!tail)
//            {
//                head = tail = list1;
//            }
//            else
//            {
//                tail->next = list1;
//                tail = tail->next;
//            }
//            list1 = list1->next;
//        }
//    }
//
//    if (list1)
//        tail->next = list1;
//    if (list2)
//        tail->next = list2;
//
//    return head;
//
//}

//合并链表（带头）
//typedef struct ListNode sl;
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    if (!list1)
//        return list2;
//    if (!list2)
//        return list1;
//
//    sl* head = (sl*)malloc(sizeof(sl));
//    sl* tail = head;
//
//    while (list1 && list2)
//    {
//        if (list1->val > list2->val)
//        {
//            tail->next = list2;
//            tail = tail->next;
//            list2 = list2->next;
//        }
//        else
//        {
//            tail->next = list1;
//            tail = tail->next;
//            list1 = list1->next;
//        }
//    }
//    if (list1)
//        tail->next = list1;
//    if (list2)
//        tail->next = list2;
//
//    return head->next;
//}

//链表分段
//ListNode* partition(ListNode* pHead, int x) {
//    struct ListNode* p1head, * p1tail, * p2head, * p2tail;
//    p1head = p1tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//    p2head = p2tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* cur = pHead;
//    while (cur)
//    {
//        if (cur->val < x)
//        {
//            p1tail->next = cur;
//            p1tail = p1tail->next;
//        }
//        else
//        {
//            p2tail->next = cur;
//            p2tail = p2tail->next;
//        }
//        cur = cur->next;
//    }
//    p1tail->next = p2head->next;
//    p2tail->next = NULL;
//    pHead = p1head->next;
//    free(p1head);
//    free(p2head);
//    return pHead;
//}


//判断回文
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* cur = head;
//    struct ListNode* per = head;
//    while (cur && cur->next)
//    {
//        cur = cur->next->next;
//        per = per->next;
//    }
//    return per;
//}
//
//struct ListNode* reverseList(struct ListNode* head) {
//    if (!head)
//        return NULL;
//    struct ListNode* rhead = NULL;
//    struct ListNode* cur = head;
//    struct ListNode* next = cur->next;
//    while (cur)
//    {
//        cur->next = rhead;
//
//        rhead = cur;
//        cur = next;
//        if (next)
//            next = next->next;
//    }
//    return rhead;
//}
//
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* head) {
//        struct ListNode* mid = middleNode(head);
//        struct ListNode* mid1 = reverseList(mid);
//
//        while (mid1)
//        {
//            if (head->val != mid1->val)
//                return false;
//            else
//            {
//                head = head->next;
//                mid1 = mid1->next;
//            }
//        }
//        return true;
//    }
//};

//判断中间结点
//typedef struct ListNode sl;
//struct ListNode* middleNode(struct ListNode* head) {
//    sl* slow = head;
//    sl* fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}


//找倒数第k个结点
//typedef struct ListNode sl;
//struct ListNode* FindKthToTail(struct ListNode* head, int k)
//{
//    sl* slow = head;
//    sl* fast = head;
//    int count = 0;
//    while (k--)
//    {
//        if (!fast)
//            return NULL;
//        fast = fast->next;
//    }
//    while (fast)
//    {
//        slow = slow->next;
//        fast = fast->next;
//    }
//    return slow;
//}

//判断回环
//typedef struct ListNode sl;
//bool hasCycle(struct ListNode* head) {
//    sl* slow = head;
//    sl* fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (slow == fast)
//            return true;
//    }
//    return false;
//}

//返回第环状的第一个结点
//typedef struct ListNode sl;
//struct ListNode* detectCycle(struct ListNode* head) {
//    sl* slow = head;
//    sl* fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (slow == fast)
//        {
//            sl* meet = slow;
//            while (meet != head)
//            {
//                head = head->next;
//                meet = meet->next;
//            }
//            return meet;
//        }
//    }
//    return NULL;
//}